<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */
 
/**
 *
 */ 
require_once( "util/AbstractMap.php" );
require_once( "util/Map.php" );
require_once( "util/MapEntry.php" );
require_once( "util/Iterator.php" );

/**
 * Class HashMap
 *
 * Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and 
 * permits null values and the null key. This class makes no guarantees as to the order of the map; in particular, it does not 
 * guarantee that the order will remain constant over time.
 * 
 * This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function 
 * disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" 
 * of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not 
 * to set the initial capacity too high (or the load factor too low) if iteration performance is important.
 * 
 * An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the 
 * number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The 
 * load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the 
 * number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly 
 * doubled by calling the rehash method.
 * 
 * As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease 
 * the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and 
 * put). The expected number of entries in the map and its load factor should be taken into account when setting its initial 
 * capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of 
 * entries divided by the load factor, no rehash operations will ever occur.
 * 
 * If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings 
 * to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table.
 *  
 * The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at 
 * any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will 
 * throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, 
 * rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
 *  
 * This class is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */
class HashMap extends AbstractMap implements Map {
	public static $DEFAULT_INITIAL_CAPACITY = 16;
	public static $MAXIMUM_CAPACITY = 1073741824; // 2 ^ 30 - this can only grow 30 times before reaching it's limit
	public static $DEFAULT_LOAD_FACTOR = .75;
	
	protected $table;
	protected $size;
	protected $capacity;
	
	public $threshold;
	public $loadFactor;
	
	protected $modCount;
	
	public function getModCount() { return $this->modCount; }
	public function getHashTable() { return $this->table; }
	public function getCapacity() { return $this->capacity; }
	
	public $NULL_KEY;
	
	public function __construct() {
		$this->loadFactor = HashMap::$DEFAULT_LOAD_FACTOR;
		$this->threshold = (int) (HashMap::$DEFAULT_LOAD_FACTOR * HashMap::$DEFAULT_INITIAL_CAPACITY);
		$this->table = array();
		$this->capacity = HashMap::$DEFAULT_INITIAL_CAPACITY;
		$this->NULL_KEY = new Object();
		$this->init();
	}
	
	public function init() { }
	
	public static function maskNull( Object $key ) {
		return ($key == null ? new Object() : $key);
	}
	
	public static function unmaskNull( Object $key ) {
		return ($key == new Object() ? null : $key);
	}
	
	public static function hash( Object $x ) {
		$h = $x->hashCode();
		
		$h += ~($h << 9);
		$h ^=  ($h >> 14);
		$h +=  ($h << 4);
		$h ^=  ($h << 10);
		return $h;
	}
	
	public static function eq( Object $x, Object $y) {
		return ($x == $y || $x->equals( $y ));
	}
	
	public static function indexFor( $h, $length ) {
		return $h & ($length - 1);
	}
	
	public function size() {
		return $this->size;
	}
	
	public function isEmpty() {
		return $this->size == 0;
	}
	
	public function get( Object $key ) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		$e = (isset($this->table[$i]) ? $this->table[$i] : null);
		
		while (true) {
			if ($e == null)
				return $e;
			if ($e->hash == $hash && HashMap::eq( $k, $e->key ))
				return $e->value;
			$e = $e->next;
		}
	}
	
	public function containsKey( Object $key ) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		$e = (isset($this->table[$i]) ? $this->table[$i] : null);
		
		while ($e != null) {
			if ($e->hash == $hash && HashMap::eq( $k, $e->key ))
				return true;
			$e = $e->next;
		}
		return false;
	}
	
	public function getEntry( Object $key ) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		$e = (isset($this->table[$i]) ? $this->table[$i] : null);
		
		while ($e != null && !($e->hash == $hash && HashMap::eq( $k, $e->key )) ) {
			$e = $e->next;
		}
		return $e;
	}
	
	public function put( Object $key, Object $value ) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		
		if (isset( $this->table[$i])) {
			for ($e = $this->table[$i]; $e != null; $e = $e->next) {
				if ($e->hash == $hash && HashMap::eq( $k, $e->key )) {
					$oldValue = $e->value;
					$e->value = $value;
					$e->recordAccess( $this );
					return $oldValue;
				}
			}
		}
		
		$this->modCount++;
		$this->addEntry( $hash, $k, $value, $i );
		return null;
	}
	
	private function putForCreate( Object $key, Object $value) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		
		for ($e = $this->table[$i]; $e != null; $e = $e->next) {
			if ($e->hash == $hash && HashMap::eq( $k, $e->key )) {
				$e->value = $value;
				return;
			}
		}
		
		$this->createEntry( $hash, $k, $value, $i );
	}
	
	public function putAllForCreate( Map $m ) {
		for ($i = $m->entrySet()->iterator(); $i->hasNext(); ) {
			$e = $i->next();
			$this->putForCreate( $e->getKey(), $e->getValue() );
		}
	}
	
	public function resize( $newCapacity ) {
		$oldCapacity = $this->capacity;
		//echo "Growing hashmap from $oldCapacity to $newCapacity<BR>";
		
		if ($oldCapacity == HashMap::$MAXIMUM_CAPACITY ) {
			$this->threshold = HashMap::$MAXIMUM_CAPACITY;
			return;
		}
		
		$newTable = $this->transfer( $newCapacity );
		$this->table = $newTable;
		$this->capacity = $newCapacity;
		$this->threshold = (int) ( $newCapacity * $this->loadFactor );
	}
	
	public function transfer( $newCapacity ) {
		$src = $this->table;
		$newTable = array();		
		
		for ($j = 0; $j < $this->capacity; $j++ ) {
			$e = (isset($src[$j]) ? $src[$j] : null);
			if ($e != null) {
				$src[$j] = null;
				do {
					$next = $e->next;
					$i = HashMap::indexFor( $e->hash, $newCapacity );
					$e->next = (isset($newTable[$i]) ? $newTable[$i] : null);
					$newTable[$i] = $e;
					$e = $next;
				} while ($e != null);
			}
		}
		
		return $newTable;
	}
	
	public function putAll( Map $m ) {
		$numKeysToBeAdded = $m->size();
		if ($numKeysToBeAdded == 0)
			return;
			
		if ($numKeysToBeAdded > $this->threshold)  {
			$targetCapacity = (int) ( $numKeysToBeAdded / $this->loadFactor + 1);
			
			if ($targetCapacity > $this->MAXIMUM_CAPACITY)
				$targetCapacity = $this->MAXIMUM_CAPACITY;
			$newCapacity = $this->table->length;
			while ($newCapacity < $targetCapacity)
				$newCapacity <<= 1;
			if ($newCapacity > $this->capacity )
				$this->resize( $newCapacity );
		}
		
		for ($i = $m->entrySet()->iterator(); $i->hasNext(); ) {
			$e = $i->next();
			$this->put( $e->getKey(), $e->getValue() );
		}
	}
	
	public function remove( Object $key ) {
		$e = $this->removeEntryForKey( $key );
		return ($e == null ? $e : $e->value);
	}
	
	public function removeEntryForKey( Object $key ) {
		$k 		= HashMap::maskNull( $key );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		
		$prev = (isset($this->table[$i]) ? $this->table[$i] : null);
		$e = $prev;
		
		while ($e != null ) {
			$next = $e->next;
			if ($e->hash == $hash && HashMap::eq( $k, $e->key )) {
				$this->modCount++;
				$this->size--;
				if ($prev == $e) 	
					$this->table[$i] = $next;
				else
					$prev->next = $next;
					
				$e->recordRemoval( $this );
				return $e;
			}
			$prev = $e;
			$e = $next;
		}
		
		return $e;
	}
	
	public function removeMapping( Object $o ) {
		if (!( $o instanceof MapEntry))
			return null;
			
		$entry = $o;
		
		$k 		= HashMap::maskNull( $entry->getKey() );
		$hash 	= HashMap::hash( $k );
		$i 		= HashMap::indexFor( $hash, $this->capacity );
		
		$prev = (isset($this->table[$i]) ? $this->table[$i] : null);
		$e = $prev;
		
		while ($e != null) {
			$next = $e->next;
			
			if ($e->hash == $hash && $e->equals( $entry )) {
				$this->modCount++;
				$this->size--;
				if ($prev == $e)
					$this->table[$i] = $next;
				else
					$prev->next = $next;
					
				$e->recordRemoval( $this );
				return $e;
			}
			
			$prev = $e;
			$e = $next;
		}
		
		return $e;
	}
	
	public function clear() {
		$this->modCount++;
		for ($i = 0; $i < $this->capacity; $i++ )
			$this->table[$i] = null;
		$this->size = 0;
	}
	
	public function containsValue( Object $value ) {
		if ($value == null) 
			return $this->containsNullValue();
			
		$tab = $this->table;
		for ($i = 0; $i < $this->capacity ; $i++ ) 
			if (isset($tab[$i])) {
				for ($e = $tab[$i]; $e != null; $e = $e->next)
					if ($value->equals($e->value))
						return true;
			}
		return false;
	}
	
	private function containsNullValue() {
		$tab = $this->table;
		for ($i = 0; $i < $this->capacity ; $i++ ) 
			if (isset($tab[$i])) {
				for ($e = $tab[$i]; $e != null; $e = $e->next)
					if ($e->value == null)
						return true;
			}
		return false;
	}
	
	public function addEntry( $hash, Object $key, Object $value, $bucketIndex ) {
		$this->table[$bucketIndex] = new HashMap_Entry( $hash, $key, $value, 
					(isset($this->table[$bucketIndex]) ? $this->table[$bucketIndex] : null) );
		if ($this->size++ >= $this->threshold)
			$this->resize( 2 * $this->capacity );
	}
	
	public function createEntry( $hash, Object $key, Object $value, $bucketIndex) {
		$this->table[$bucketIndex] = new HashMap_Entry( $hash, $key, $value, 
					(isset($this->table[$bucketIndex]) ? $this->table[$bucketIndex] : null) );
		$this->size++;
	}
	
	public function newKeyCollectionIterator() {
		return new HashMap_KeyIterator( $this );
	}
	public function newValueCollectionIterator() {
		return new HashMap_ValueIterator( $this );
	}
	public function newEntryCollectionIterator() {
		return new HashMap_EntryIterator( $this );
	}
	
	// Views
	
	private $entrySet = null;
	
	public function keySet() {
		$ks = $this->key_set;
		return ($ks != null ? $ks : ( $this->key_set = new HashMap_KeySet( $this )));
	}
	
	public function values() {
		$vs = $this->values;
		return ($vs != null ? $vs : ( $this->values = new HashMap_ValuesCollection( $this ) ));
	}
	
	public function entrySet() {
		$es = $this->entrySet;
		return ($es != null ? $es : ( $this->entrySet = new HashMap_EntrySet( $this ) ));
	}
	

}

/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_Entry implements MapEntry {
	public $key;
	public $value;
	public $hash;
	public $next;
	
	public function __construct( $h, Object $k = null, Object $v = null, HashMap_Entry $n = null ) {
		$this->value = $v;
		$this->next = $n;
		$this->key = $k;
		$this->hash = $h;
	}
	
	public function getKey() {
		return HashMap::unmaskNull( $this->key );
	}
	
	public function getValue() {
		return $this->value;
	}
	
	public function setValue( Object $newValue ) {
		$oldValue = $this->value;
		$this->value = $newValue;
		return $oldValue;
	}
	
	public function equals( Object $o ) {
		if ( ! ($o instanceof MapEntry ))
			return false;
			
		$e = $o;
		$k1 = $this->getKey();
		$k2 = $e->getKey();
		
		if ($k1 == $k2 || ( $k1 != null && $k1->equals( $k2 ) )) {
			$v1 = $this->getValue();
			$v2 = $e->getValue();
			if ($v1 == $v2 || ( $v1 != null && $v1->equals( $v2 ) )) 
				return true;
		}
		return false;
	}
	
	public function hashCode() {
		return ($this->key == NULL_KEY ? 0 : $this->key->hashCode()) ^ ( $this->value == null ? 0 : $this->value->hashCode() );
	}
	
	public function toString() {
		return $this->getKey() . "=" . $this->getValue();
	}
	
	public function recordAccess( HashMap $m ) {
	}
	
	public function recordRemoval( HashMap $m ) {
	}
}
/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
abstract class HashMap_Iterator implements CollectionIterator {
	private $map;

	private $next;				// next entry to return
	private $expectedModCount;	// for fast fail
	private $index;				// current slot
	private $current;			// current entry
	
	public function __construct( HashMap $map ) {
		$this->expectedModCount = $map->getModCount();
		$t = $map->getHashTable();
		$i = $map->getCapacity();
		$n = null;
		
		if ($map->size() != 0) {
			while ($i > 0 && ($n = (isset($t[--$i]) ? $t[$i] : null)) == null) {
				
			}
		}
		$this->next = $n;
		$this->index = $i;
		$this->map = $map;
	}
	
	public function hasNext() {
		return $this->next != null;
	}
	
	public function nextEntry() {
		if ($this->map->getModCount() != $this->expectedModCount) 
			throw new ConcurrentModificationException();
			
		$e = $this->next;
		if ($e == null )
			throw new NoSuchElementException();
			
		$n = $e->next;
		$t = $this->map->getHashTable();
		$i = $this->index;
		
		while ($n == null && $i > 0) 
			$n = (isset($t[--$i]) ? $t[$i] : null);
		$this->index = $i;
		$this->next = $n;
		return $this->current = $e;
	}
	
	public function remove() {
		if ($this->current == null) 
			throw new IllegalStateException();
		if ($this->map->getModCount != $this->expectedModCount )
			throw new ConcurrentModificationException();
		
		$k = $this->current->key;
		$this->current = null;
		$this->map->removeEntryForKey( $k );
		$this->expectedModCount = $this->map->getModCount();
	}
}
/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_ValueIterator extends HashMap_Iterator {
	public function next() {
		return $this->nextEntry()->getValue();
	}
	
	public function getNext() {
		return $this->nextEntry()->getValue();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}
/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_KeyIterator extends HashMap_Iterator {
	public function next() {
		return $this->nextEntry()->getKey();
	}
	public function getNext() {
		return $this->nextEntry()->getKey();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}
/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_EntryIterator extends HashMap_Iterator {
	public function next() {
		return $this->nextEntry();
	}
	public function getNext() {
		return $this->nextEntry();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
}

/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_KeySet extends AbstractSet {
	private $map;
	
	public function __construct( HashMap $map ) {
		$this->map = $map;
	}
	
	public function iterator() {
		return $this->map->newKeyCollectionIterator();
	}
	public function size() {
		return $this->map->size();
	}
	public function contains( Object $o ) {
		return $this->map->containsKey( $o );
	}
	public function remove( Object $o ) {
		return $this->map->removeEntryForKey( $o ) != null;
	}
	public function clear() {
			$this->map->clear();
	}
}

/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_ValuesCollection extends AbstractCollection {
	private $map;
	
	public function __construct( HashMap $map ) {
		$this->map = $map;
	}
	
	public function iterator() {
		return $this->map->newValueCollectionIterator();
	}
	public function size() {
		return $this->map->size();
	}
	public function contains( Object $o ) {
		return $this->map->containsKey( $o );
	}
	public function clear() {
			$this->map->clear();
	}
}

/**
 *
 *
 * @author $Author$
 * @version $Id: HashMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class HashMap_EntrySet extends AbstractSet {
	private $map;
	
	public function __construct( HashMap $map ) {
		$this->map = $map;
	}
	
	public function iterator() {
		return $this->map->newEntryCollectionIterator();
	}
	public function size() {
		return $this->map->size();
	}
	public function contains( Object $o ) {
		if (! ($o instanceof MapEntry))
			return false;
			
		$e = $o;
		$canidate = $this->map->getEntry( $e->getKey() );
		return $canidate != null && $canidate->equals( $e );
	}
	public function remove( Object $o ) {
		return $this->map->removeMapping( $o ) != null;
	}
	public function clear() {
			$this->map->clear();
	}
}



?>

